# The function does not handle empty lists!
proc print_list {the_list} {
    puts -nonewline {[}
    # lrange is inclusive on both ends!
    foreach x [lrange $the_list 0 [expr [llength $the_list] - 2]] {
        puts -nonewline "$x, "
    }
    puts "[lindex $the_list [expr [llength $the_list] - 1]]\]"
}

proc quicksort {the_list} {
    if {[llength $the_list] == 0} {
        return $the_list
    } elseif {[llength $the_list] == 1} {
        return $the_list
    } else {
        set pivot [lindex $the_list 0]
        set lte_pivot [list]
        set gt_pivot [list]

        foreach x [lrange $the_list 1 end] {
            if {$x <= $pivot} {
                lappend lte_pivot $x
            } else {
                lappend gt_pivot $x
            }
        }
        return [concat [quicksort $lte_pivot] $pivot [quicksort $gt_pivot]]
    }

}

proc mergesort {list_A list_B} {
    set sorted_list [list]
    set pos_A 0
    set pos_B 0

    while {$pos_A != [llength $list_A] && $pos_B != [llength $list_B]} {
        if {[lindex $list_A $pos_A] <= [lindex $list_B $pos_B]} {
            lappend sorted_list [lindex $list_A $pos_A]
            incr pos_A
        } else {
            lappend sorted_list [lindex $list_B $pos_B]
            incr pos_B
        }
    }
    return [concat $sorted_list [lrange $list_A $pos_A end] \
                                [lrange $list_B $pos_B end]]
}


# Generate random list of integers.
set random_ints [list]
for {set x [lindex $argv 0]} {$x > 0} {set x [expr $x - 1]} {
    lappend random_ints $x
}

# Split into two lists.
set list_A [list]
set list_B [list]
set list_midpoint [expr [llength $random_ints] / 2]
for {set x 0} {$x < $list_midpoint} {incr x} {
    lappend list_A [lindex $random_ints $x]
}
for {set x $list_midpoint} {$x < [llength $random_ints]} {incr x} {
    lappend list_B [lindex $random_ints $x]
}

# Sort the two lists individually.
set list_A [quicksort $list_A]
set list_B [quicksort $list_B]

# Merge and sort the two lists.
print_list [mergesort $list_A $list_B]
